package algorithm.sorty.sort.compare;

import algorithm.sorty.Sort;

/**
 * @Description: 冒泡排序
 * @Author Ammar
 * @Create 2023/4/30 01:53
 */
public class BubbleSort<T extends Comparable<T>> extends Sort<T> {

    /**
     * 针对部分有序和完全有序优化
     */
    @Override
    public void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            // 当数组完全有序时，一轮扫描就可以结束
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                // 进到这里，说明数组不是完全有序
                if (compare(begin, begin - 1) < 0) {
                    // 交换位置
                    swap(begin, begin - 1);
                    // 记录最后一次交换的位置，下一轮扫描到这里就可以结束
                    sortedIndex = begin;
                }
            }
            // 一轮扫描结束，更新end
            end = sortedIndex;
        }
    }

    /**
     * 冒泡排序最初的写法
     */
    public void sort1() {
        // 从后往前，每次都把最大的数放到最后
        for (int end = array.length - 1; end > 0; end--) {
            // 避免数组已经有序，提前退出
            // 从前往后，每次都把最小的数放到最前
            for (int begin = 1; begin <= end; begin++) {
                if (compare(begin, begin - 1) < 0) {
                    // 交换位置
                    swap(begin, begin - 1);
                }
            }
        }
    }

    /**
     * 针对完全有序优化
     */
    public void sort2() {
        // 从后往前，每次都把最大的数放到最后
        for (int end = array.length - 1; end > 0; end--) {
            // 避免数组已经有序，提前退出
            boolean sorted = true;
            // 从前往后，每次都把最小的数放到最前
            for (int begin = 1; begin <= end; begin++) {
                if (compare(begin, begin - 1) < 0) {
                    // 交换位置
                    swap(begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }
}
